Matematika Diskret: Dasar-Dasar Penghitungan

Penghitungan adalah seni menentukan ukuran himpunan berhingga tanpa pekerjaan melelahkan dari enumerasi fisik. Dengan memanfaatkan struktur logis, kita dapat menyelesaikan masalah mulai dari kombinasi menu sederhana hingga permutasi kriptografi yang kompleks.

Logika "ATAU" dan "DAN"

Dua pilar mendukung seluruh bidang kombinatorika. Aplikasinya sangat bergantung pada apakah kita melihat suatu tugas sebagai satu pilihan dari berbagai kategori atau sebagai rangkaian pilihan berturut-turut.

Prinsip Penjumlahan (Aturan Jumlah)

Jika suatu himpunan $X$ dibagi menjadi subset-subset yang saling lepas $X_1, X_2, \dots, X_n$, maka jumlah total elemen $|X|$ adalah jumlah ukuran dari subset-subset tersebut:

$$|X| = |X_1| + |X_2| + \dots + |X_n|$$

Analogi: Memilih makanan di Kay’s Quick Lunch dengan memilih salah satu antara sandwich dari menu Makanan Utama ATAU camilan dari menu Camilan. Anda tidak bisa memilih keduanya; Anda hanya memilih satu item.

Prinsip Perkalian (Aturan Produk)

Jika suatu aktivitas terdiri dari $t$ langkah berturut-turut, di mana langkah ke-$i$ memiliki $n_i$ kemungkinan hasil, maka jumlah total cara untuk menyelesaikan tugas tersebut adalah hasil kali dari kemungkinan pada setiap langkah:

$$N = n_1 \times n_2 \times \dots \times n_t$$

Analogi: Mengkonfigurasi truk "Big Pickup". Anda harus memilih mesin (5 pilihan) DAN gaya kabin (3 pilihan). Total konfigurasi sama dengan $5 \times 3 = 15$.

Implementasi Kode dan Kompleksitas

Dalam ilmu komputer, prinsip-prinsip ini muncul dalam struktur loop. Loop yang berurutan merepresentasikan Prinsip Penjumlahan, sedangkan loop bersarang merepresentasikan Prinsip Perkalian.

// Prinsip Penjumlahan (m + n eksekusi)

untuk i = 1 sampai m: println(i)

untuk j = 1 sampai n: println(j)

// Prinsip Perkalian (m * n eksekusi)

untuk i = 1 sampai m:

untuk j = 1 sampai n:

println(i, j)

🎯 Prinsip Utama

Kenali berdasarkan kata kunci: "ATAU" menunjukkan Penjumlahan (pilihan yang saling eksklusif), sedangkan "DAN" atau "Berturut-turut" menunjukkan Perkalian (langkah-langkah independen dalam urutan).

PERTANYAAN 1

Berapa banyak hidangan di Kay's Quick Lunch (Gambar 6.1.1) yang terdiri dari satu camilan dan satu minuman, jika ada 3 camilan dan 4 minuman?

PERTANYAAN 2

Dalam potongan kode yang diberikan, berapa kali pernyataan print dieksekusi secara total? [Kode: untuk i = 1 sampai m, println(i), untuk j = 1 sampai n, println(j)]

m × n

$m + n$

$m^n$

$n^m$

PERTANYAAN 3

Berapa banyak string panjang 3 yang dapat dibentuk menggunakan huruf-huruf {A, B, C, D, E} jika pengulangan diperbolehkan?

125

243

PERTANYAAN 4

Dengan kunci publik (n=713, e=29), berapa enkripsi dari pesan M = 333?

333

557

128

712

PERTANYAAN 5

Berapa banyak string panjang 3 yang menggunakan huruf-huruf {A, B, C, D, E} yang mengandung huruf A minimal satu kali (pengulangan diperbolehkan)?

125

Tantangan: Pemikiran Kombinatorika Lanjutan

Truk, Segitiga, dan Lubang Merpati

Skenario: Truk besar menarik karena cara mereka yang tampak tak terbatas untuk dipersonalisasi. Artikel di New York Times menyiratkan bahwa Anda butuh keterampilan matematika seperti Will Hunting untuk menghitung semua konfigurasi. Mari kita analisis model dengan 5 pilihan mesin (3.9L V6, 5.2L V8, 5.9L V8, 5.9L Turbo-diesel, 8L V10).

Definisikan urutan leksikografis dan jelaskan mengapa hal ini berguna dalam struktur penghitungan.

Solusi: Urutan leksikografis adalah generalisasi dari urutan alfabetik kata-kata dalam kamus ke dalam urutan simbol terurut. Diberikan dua urutan $a_1...a_n$ dan $b_1...b_n$, kita mengatakan $a < b$ jika pada indeks pertama $i$ di mana $a_i \neq b_i$, kita memiliki $a_i < b_i$. Ini berguna karena memberikan cara sistematis untuk mencantumkan semua permutasi atau kombinasi tanpa penghilangan atau pengulangan.

Apa itu permutasi dari $x_1, \dots, x_n$? Berikan definisi formal.

Solusi: Permutasi dari suatu himpunan objek yang berbeda adalah susunan terurut dari objek-objek tersebut. Untuk himpunan dengan $n$ elemen, permutasi adalah bijeksi dari himpunan $\{1, 2, \dots, n\}$ ke himpunan itu sendiri, di mana urutan elemen dalam urutan hasilnya penting.

Buktikan bahwa jika lima kartu dipilih dari dek kartu standar 52 kartu, minimal dua kartu memiliki jenis yang sama.

Solusi: Ini adalah aplikasi dari Prinsip Lubang Merpati. Ada 4 jenis kartu yang mungkin ("lubang") dan 5 kartu dipilih ("merpati"). Karena $5 > 4$, menurut Prinsip Lubang Merpati, minimal satu jenis harus mengandung $\lceil 5/4 \rceil = 2$ kartu. Maka, minimal dua kartu harus memiliki jenis yang sama.

Dalam berapa cara kita dapat memilih delapan bola dari tas yang berisi bola merah, biru, dan kuning (minimal 8 dari masing-masing)? (Kesulitan: Kata Kunci: 18, Panjang: Pendek)

Solusi: Ini adalah masalah kombinasi dengan pengulangan. Gunakan rumus bintang dan batang $C(n+r-1, r)$ dengan $n=3$ kategori dan $r=8$ pemilihan: $C(3+8-1, 8) = C(10, 8) = C(10, 2) = (10 \times 9) / 2 = 45$ cara.